package fast_slow_pointers;

import Node.ListNode;

/**
 * 查找单链表倒数第k个链表
 */
public class FindFromEnd {

    public ListNode findFromEnd(ListNode head, int k) {
        ListNode p1 = head;
        // p1先走k步
        for (int i = 0; i < k; i++) {
            p1 = p1.next;
        }
        ListNode p2 = head;
        // p1和p2同时走n-k步
        while (p1 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }

        // p2现在指向n-k+1个节点，即倒数k个节点
        return p2;
    }
}
